

//冒泡排序算法，它是最慢的排序算法之一，但也是一种最容易实现的排序算法
//每次循环都会把当前最大的值挪到最右边
//如果碰到的值比当前的最大值还大，那么把更大的值与当前值交换，成为新的最大值一直与后面的值比较，直到此次最大值挪到最右边
//重复上述操作依次循环
//冒泡一：算法复杂度：O(n^2)，即n的平方
let array = [2,5,61,74,0,64,1,74,20,632,4125,1,45,20,31,12,48,2] //随机生成的一组数组

function bubbleSort(arr){ //注意内外层for循环在干什么
    for(let i = 0; i < arr.length; i++){ //外层for循环是遍历整个数组的每一个值
        for(let j = 0; j < arr.length; j++){ //内层for循环是在此次外层for循环的基础上将此次遍历到的值与数组中每一个值做遍历比较
            if(arr[i] < arr[j]){ //这里前者 > 后者就是从大到小排序，改成 < 就是从小到大排序
                [arr[i],arr[j]] = [arr[j],arr[i]] //使用解构赋值来交换值得位置
            }
        }
    }
}
bubbleSort(array)
console.log(array)

//冒泡二：算法复杂度：n n-1 n-2 n-3 ... 1，即等差数列 S = n(n+1)/2 = (n^2+n)/2，大致为上个冒泡的复杂度一半
//控制循环起始处
let array1 = [2,5,61,74,0,64,1,74,20,632,4125,1,45,20,31,12,48,2] //随机生成的一组数组

function bubbleSort1(arr){ //注意内外层for循环在干什么
    for(let i = 0; i < arr.length; i++){ //外层for循环是遍历整个数组的每一个值
        for(let j = i; j < arr.length; j++){ //内层for循环是在此次外层for循环的基础上将此次遍历到的值与剩下的每一个值做遍历比较
            //内层循环将j的起始改为i，因为之前每次都把最大值挪到最右边，所以接下来每次都无需与之前的最大值进行比较
            if(arr[i] < arr[j]){ //这里前者 > 后者就是从大到小排序，改成 < 就是从小到大排序
                [arr[i],arr[j]] = [arr[j],arr[i]] //使用解构赋值来交换值得位置
            }
        }
    }
}
bubbleSort1(array1)
console.log(array1)

//冒泡三：
//控制循环结束处，两者复杂度相同
let array2 = [2,5,61,74,0,64,1,74,20,632,4125,1,45,20,31,12,48,2] //随机生成的一组数组

function bubbleSort2(arr){ //注意内外层for循环在干什么
    for(let i = 0; i < arr.length; i++){ //外层for循环是遍历整个数组的每一个值
        for(let j = 0; j < arr.length - i; j++){ //内层for循环是在此次外层for循环的基础上将此次遍历到的值与剩下的每一个值做遍历比较
            //内层循环将j的终点改为length-i
            if(arr[j] > arr[j+1]){ //这里前者 > 后者就是从大到小排序，改成 < 就是从小到大排序
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]] //使用解构赋值来交换值得位置
            }
        }
    }
}
bubbleSort2(array2)
console.log(array2)

//随机生成数组的函数
function creatArray(length){
    let array = new Array(length)
    for(let i = 0, len = length; i < len; i++){
        array[i] = Math.floor(Math.random()*length)
    }
    return array
}
let myArray = creatArray(10000)

//冒泡四：和冒泡三类似，就是把内层for循环换成了sortCount

function bubbleSort3(arr){
    let isDone = false //初始化一个遍历状态，默认为false
    let sortCount = 0 //初始化一个遍历次数，默认值为0

    do{
        isDone = false
        for(let j = 0; j < arr.length - sortCount; j++){
            //内层循环将j的终点改为length-sortCount
            if(arr[j] > arr[j+1]){ //这里前者 > 后者就是从大到小排序，改成 < 就是从小到大排序
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]] //使用解构赋值来交换值得位置
                isDone = true
            }
        }
        sortCount++ //每次遍历完一次，加1
    }while(isDone)
}
console.time(`冒泡排序四的时间`) //计算时间的方法，里面的参数必须保持一致
bubbleSort3(myArray)
console.timeEnd(`冒泡排序四的时间`)

